package checkValidGrid;
class Solution {
    int[][] dir = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
    public boolean checkValidGrid(int[][] grid) {
        if(grid[0][0]!=0)return false;
        return dfs(grid,0,0,1);
    }
    private boolean dfs(int[][] grid,int x,int y,int cur) {
        //    System.out.println(x+" "+y+" "+cur);
        if(cur == grid.length*grid[0].length) return true;
        for (int i = 0; i < dir.length; i++) {
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];
            if(check(nextX,nextY,grid,cur)) {
                return dfs(grid,nextX,nextY,cur+1);
            }
        }
        return false;
    }
    private boolean check(int x,int y,int[][] grid,int cur) {
        if(x<0||y<0||x>=grid.length||y>=grid[0].length) return false;
        return grid[x][y] == cur;
    }
}
